################################################################################
#       Copyright (C) 2010 Michael Yurko <myurko@gmail.com>
#
#This file is part of pyQAP.
#
#pyQAP is free software: you can redistribute it and/or modify
#it under the terms of the GNU General Public License as published by
#the Free Software Foundation, either version 2 of the License, or
#(at your option) any later version.
#
#pyQAP is distributed in the hope that it will be useful,
#but WITHOUT ANY WARRANTY; without even the implied warranty of
#MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#GNU General Public License for more details.
#
#You should have received a copy of the GNU General Public License
#along with pyQAP.  If not, see <http://www.gnu.org/licenses/>.
################################################################################

'''
Problems and problem generators for the QAP
'''
import numpy as np
import classes
import vars

def num_gen(file):
    '''
    A generator which returns numbers from a file.
    
    Examples:
    
    Tested in QAPLIB.
    '''
    while True:
        for n_str in file.next().split():
            try:
                n = float(n_str)
                yield n
            except ValueError:
                pass

def QAPLIB(name, directory=vars.problem_directory):
    """
    Returns a problem instance from the QAPLIB by parsing the .dat file.
    
    Examples:
    
    >>> QAPLIB('nug12')
    QAP of size 12 with the flow matrix
    [[ 0.  1.  2.  3.  1.  2.  3.  4.  2.  3.  4.  5.]
     [ 1.  0.  1.  2.  2.  1.  2.  3.  3.  2.  3.  4.]
     [ 2.  1.  0.  1.  3.  2.  1.  2.  4.  3.  2.  3.]
     [ 3.  2.  1.  0.  4.  3.  2.  1.  5.  4.  3.  2.]
     [ 1.  2.  3.  4.  0.  1.  2.  3.  1.  2.  3.  4.]
     [ 2.  1.  2.  3.  1.  0.  1.  2.  2.  1.  2.  3.]
     [ 3.  2.  1.  2.  2.  1.  0.  1.  3.  2.  1.  2.]
     [ 4.  3.  2.  1.  3.  2.  1.  0.  4.  3.  2.  1.]
     [ 2.  3.  4.  5.  1.  2.  3.  4.  0.  1.  2.  3.]
     [ 3.  2.  3.  4.  2.  1.  2.  3.  1.  0.  1.  2.]
     [ 4.  3.  2.  3.  3.  2.  1.  2.  2.  1.  0.  1.]
     [ 5.  4.  3.  2.  4.  3.  2.  1.  3.  2.  1.  0.]]
    and distance matrix
    [[  0.   5.   2.   4.   1.   0.   0.   6.   2.   1.   1.   1.]
     [  5.   0.   3.   0.   2.   2.   2.   0.   4.   5.   0.   0.]
     [  2.   3.   0.   0.   0.   0.   0.   5.   5.   2.   2.   2.]
     [  4.   0.   0.   0.   5.   2.   2.  10.   0.   0.   5.   5.]
     [  1.   2.   0.   5.   0.  10.   0.   0.   0.   5.   1.   1.]
     [  0.   2.   0.   2.  10.   0.   5.   1.   1.   5.   4.   0.]
     [  0.   2.   0.   2.   0.   5.   0.  10.   5.   2.   3.   3.]
     [  6.   0.   5.  10.   0.   1.  10.   0.   0.   0.   5.   0.]
     [  2.   4.   5.   0.   0.   1.   5.   0.   0.   0.  10.  10.]
     [  1.   5.   2.   0.   5.   5.   2.   0.   0.   0.   5.   0.]
     [  1.   0.   2.   5.   1.   4.   3.   5.  10.   5.   0.   2.]
     [  1.   0.   2.   5.   1.   0.   3.   0.  10.   0.   2.   0.]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]
    >>> QAPLIB('esc32a')
    QAP of size 32 with the flow matrix
    [[ 0.  1.  1. ...,  0.  0.  0.]
     [ 1.  0.  1. ...,  0.  0.  0.]
     [ 1.  1.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    and distance matrix
    [[ 0.  0.  0. ...,  3.  3.  4.]
     [ 0.  0.  1. ...,  2.  4.  3.]
     [ 0.  1.  0. ...,  4.  2.  3.]
     ..., 
     [ 3.  2.  4. ...,  0.  1.  0.]
     [ 3.  4.  2. ...,  1.  0.  0.]
     [ 4.  3.  3. ...,  0.  0.  0.]]
    and linear cost matrix
    [[ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    >>> QAPLIB('jen4')
    QAP of size 4 with the flow matrix
    [[ 0.  5.  2.  7.]
     [ 0.  0.  3.  8.]
     [ 0.  0.  0.  3.]
     [ 0.  0.  0.  0.]]
    and distance matrix
    [[   0.   80.  150.  170.]
     [  80.    0.  130.  100.]
     [ 150.  130.    0.  120.]
     [ 170.  100.  120.    0.]]
    and linear cost matrix
    [[ 0.  0.  0.  0.]
     [ 0.  0.  0.  0.]
     [ 0.  0.  0.  0.]
     [ 0.  0.  0.  0.]]
    >>> QAPLIB('sko100f')
    QAP of size 100 with the flow matrix
    [[  0.   1.   2. ...,  16.  17.  18.]
     [  1.   0.   1. ...,  15.  16.  17.]
     [  2.   1.   0. ...,  14.  15.  16.]
     ..., 
     [ 16.  15.  14. ...,   0.   1.   2.]
     [ 17.  16.  15. ...,   1.   0.   1.]
     [ 18.  17.  16. ...,   2.   1.   0.]]
    and distance matrix
    [[ 0.  5.  1. ...,  4.  0.  0.]
     [ 5.  0.  4. ...,  0.  0.  0.]
     [ 1.  4.  0. ...,  0.  2.  1.]
     ..., 
     [ 4.  0.  0. ...,  0.  3.  1.]
     [ 0.  0.  2. ...,  3.  0.  2.]
     [ 0.  0.  1. ...,  1.  2.  0.]]
    and linear cost matrix
    [[ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    """
    #open file
    with file(directory+name+".dat", "r") as dat:
        #get size
        n = int(dat.next())
        
        #create generator
        gen = num_gen(dat)
        
        #parse flow matrix
        f = np.empty((n,n), dtype = np.float)
        for i in xrange(n):
            for j in xrange(n):
                f[i, j] = gen.next()
        
        #parse distance matrix
        d = np.empty((n,n), dtype = np.float)
        for i in xrange(n):
            for j in xrange(n):
                d[i, j] = gen.next()
        
    return classes.Problem(f,d)
    
def QAPLIB_sln(name, directory=vars.problem_directory):
    '''
    Return the solution corresponding to the given QAPLIB problem.
    Note: time, nodes, etc. will be -1 to indicate that it was not
    computed with this library.
    
    Examples:
    
    >>> QAPLIB_sln('nug12')
    QAP Solution: [ 11.   6.   8.   2.   3.   7.  10.   0.   4.   5.   9.   1.] Cost: 578.000000 Nodes visited: -1.000000 Total time: -1.000000
    >>> QAPLIB_sln('esc32a')
    Traceback (most recent call last):
      ...
    IOError: [Errno 2] No such file or directory: '...esc32a.sln'
    >>> QAPLIB_sln('sko100f')
    QAP Solution: [ 77.  58.  63.  41.  30.  39.  57.  14.  89.  72.  16.  74.  97.  18.  54.
       9.  51.  29.  42.  85.  26.  47.  69.  45.  87.  23.  37.   5.  65.   1.
      21.   0.  13.  40.  10.  36.  49.   7.  78.  60.  38.  33.  43.  55.  46.
      82.  34.  59.  92.  68.  66.  35.  25.  90.   8.  94.  73.  70.  67.  15.
      61.  81.  44.  75.  83.  48.  24.  84.   6.  20.  52.  17.  11.  71.  86.
      88.   4.  99.  28.   2.  93.  19.   3.  80.  22.  50.  64.  98.  56.  31.
      91.  62.  95.  32.  27.  12.  53.  76.  79.  96.] Cost: 149036.000000 Nodes visited: -1.000000 Total time: -1.000000
    >>> QAPLIB_sln('had16')
    QAP Solution: [  8.   3.  15.   0.   6.   7.   5.  13.  14.  10.  11.   9.   4.   2.   1.
      12.] Cost: 3720.000000 Nodes visited: -1.000000 Total time: -1.000000
    '''
    #open file
    with file(directory+name+".sln", "r") as dat:
        #get size and solution
        line = dat.next().split()
        n = int(line[0])
        cost = float(line[1])
        #get solution array
        sol = np.empty((n))
        gen = num_gen(dat)
        for i in xrange(n):
            sol[i] = int(gen.next())-1     #offset to start at 0
    return classes.Solution(sol, cost, -1, -1)
            

def QAPLIB_list(path = vars.problem_directory):
    """
    Returns a list of the QAPLIB problems.
    
    Examples:
    
    >>> QAPLIB_list()
    ['gin50', 'nug16b', 'tai17a', 'sko100b', 'esc64a', 'tai20b', 'sko72', 'chr12c', 'esc16d', 'tai256c', 'ste36c', 'sko81', 'tai12a', 'tai25b', 'lipa30a', 'nug20', 'ste36b', 'gin80', 'tai40a', 'Inst100', 'tai30a', 'scr20', 'chr25a', 'tai60a', 'sko64', 'gin40', 'nug17', 'tai64c', 'esc32e', 'kra30b', 'nug18', 'tho40', 'lipa40a', 'sko100a', 'Inst40', 'Inst20', 'esc32d', 'Inst30', 'sko100d', 'tai12b', 'esc32g', 'had18', 'bur26g', 'nug15', 'lipa20b', 'tai10b', 'tai25a', 'sko42', 'sko56', 'tai15a', 'chr15b', 'gin60', 'lipa70a', 'nug12', 'had14', 'sko100f', 'gin20', 'chr15c', 'esc16b', 'nug16a', 'chr22b', 'bur26e', 'sko49', 'kra32', 'esc16a', 'scr15', 'bur26h', 'esc32a', 'tai150b', 'esc16i', 'ste36a', 'els19', 'lipa50b', 'wil100', 'chr20a', 'esc32b', 'bur26d', 'tai80b', 'esc32f', 'sko100c', 'lipa20a', 'lipa60b', 'esc16e', 'esc16c', 'esc128', 'Inst60', 'tai100b', 'nug21', 'chr20c', 'sko90', 'lipa90b', 'gin30', 'lipa60a', 'had12', 'tai10a', 'had16', 'jen4', 'Inst70', 'esc32h', 'bur26f', 'nug14', 'tho30', 'esc16g', 'nug28', 'tai60b', 'kra30a', 'chr20b', 'Inst50', 'gin200', 'chr12a', 'bur26b', 'gin70', 'tai35a', 'Inst200', 'lipa30b', 'gin100', 'Inst150', 'had20', 'tai80a', 'nug30', 'lipa50a', 'rou15', 'tai20a', 'tai35b', 'bur26a', 'esc32c', 'chr18a', 'tai40b', 'lipa80b', 'lipa70b', 'tho150', 'chr12b', 'chr18b', 'nug27', 'scr12', 'chr22a', 'bur26c', 'tai50a', 'gin150', 'chr15a', 'tai50b', 'lipa80a', 'sko100e', 'nug24', 'tai15b', 'esc16h', 'nug22', 'Inst80', 'rou12', 'wil50', 'nug25', 'esc16f', 'tai100a', 'tai30b', 'rou20', 'lipa90a', 'esc16j', 'lipa40b']
    """
    import os
    problems = []
    for root, dirs, files in os.walk(path):
        for name in files:      
            if name[-1] == "t":
                problems.append(name[0:-4])
    return problems

def random(n, seed = vars.seed_standard):
    """
    Returns a random, symmetric Problem of size n.
    
    Examples:
    
    >>> np.random.seed(123)
    >>> random(5)
    QAP of size 5 with the flow matrix
    [[ 0.          0.12696983  0.26047601  0.37674972  0.45137647]
     [ 0.12696983  0.          0.12310214  0.37301223  0.12944068]
     [ 0.26047601  0.12310214  0.          0.82038836  0.2288873 ]
     [ 0.37674972  0.37301223  0.82038836  0.          0.59478359]
     [ 0.45137647  0.12944068  0.2288873   0.59478359  0.        ]]
    and distance matrix
    [[ 0.          0.96671784  0.89723652  0.33622174  0.84025508]
     [ 0.96671784  0.          0.5430262   0.44799682  0.85987871]
     [ 0.89723652  0.5430262   0.          0.35205354  0.77678375]
     [ 0.33622174  0.44799682  0.35205354  0.          0.13755356]
     [ 0.84025508  0.85987871  0.77678375  0.13755356  0.        ]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.]]
    >>> random(10)
    QAP of size 10 with the flow matrix
    [[ 0.          0.12696983  0.26047601  0.37674972  0.45137647  0.12310214
       0.37301223  0.12944068  0.82038836  0.2288873 ]
     [ 0.12696983  0.          0.59478359  0.85289978  0.14622723  0.57401177
       0.590426    0.34044494  0.9195404   0.86154929]
     [ 0.26047601  0.59478359  0.          0.40517876  0.17091717  0.64166617
       0.46235433  0.40113122  0.11796713  0.41403366]
     [ 0.37674972  0.85289978  0.40517876  0.          0.59592532  0.09973676
       0.01654451  0.09593887  0.83879627  0.73259152]
     [ 0.45137647  0.14622723  0.17091717  0.59592532  0.          0.56065718
       0.13876812  0.94225634  0.63069955  0.43348979]
     [ 0.12310214  0.57401177  0.64166617  0.09973676  0.56065718  0.
       0.86260898  0.0857089   0.14982485  0.84893827]
     [ 0.37301223  0.590426    0.46235433  0.01654451  0.13876812  0.86260898
       0.          0.32955081  0.61937849  0.67239782]
     [ 0.12944068  0.34044494  0.40113122  0.09593887  0.94225634  0.0857089
       0.32955081  0.          0.38699906  0.98894936]
     [ 0.82038836  0.9195404   0.11796713  0.83879627  0.63069955  0.14982485
       0.61937849  0.38699906  0.          0.37038179]
     [ 0.2288873   0.86154929  0.41403366  0.73259152  0.43348979  0.84893827
       0.67239782  0.98894936  0.37038179  0.        ]]
    and distance matrix
    [[ 0.          0.96671784  0.89723652  0.33622174  0.84025508  0.5430262
       0.44799682  0.85987871  0.35205354  0.77678375]
     [ 0.96671784  0.          0.13755356  0.23550748  0.58986877  0.06126996
       0.24534982  0.98472874  0.03777169  0.75356885]
     [ 0.89723652  0.13755356  0.          0.34352588  0.39465901  0.27459243
       0.87137165  0.61058827  0.70218436  0.34234521]
     [ 0.33622174  0.23550748  0.34352588  0.          0.19986426  0.73459622
       0.4813845   0.49730633  0.89733326  0.75872436]
     [ 0.84025508  0.58986877  0.39465901  0.19986426  0.          0.47147793
       0.09446113  0.13409924  0.63956822  0.15584706]
     [ 0.5430262   0.06126996  0.27459243  0.73459622  0.47147793  0.
       0.6830463   0.56610253  0.47745445  0.14014442]
     [ 0.44799682  0.24534982  0.87137165  0.4813845   0.09446113  0.6830463
       0.          0.63407411  0.39504264  0.80998032]
     [ 0.85987871  0.98472874  0.61058827  0.49730633  0.13409924  0.56610253
       0.63407411  0.          0.54475875  0.98498291]
     [ 0.35205354  0.03777169  0.70218436  0.89733326  0.63956822  0.47745445
       0.39504264  0.54475875  0.          0.56294193]
     [ 0.77678375  0.75356885  0.34234521  0.75872436  0.15584706  0.14014442
       0.80998032  0.98498291  0.56294193  0.        ]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]
    >>> random(20)
    QAP of size 20 with the flow matrix
    [[ 0.          0.12696983  0.26047601  0.37674972  0.45137647  0.12310214
       0.37301223  0.12944068  0.82038836  0.2288873   0.59478359  0.85289978
       0.14622723  0.57401177  0.590426    0.34044494  0.9195404   0.86154929
       0.40517876  0.17091717]
     [ 0.12696983  0.          0.64166617  0.46235433  0.40113122  0.11796713
       0.41403366  0.59592532  0.09973676  0.01654451  0.09593887  0.83879627
       0.73259152  0.56065718  0.13876812  0.94225634  0.63069955  0.43348979
       0.86260898  0.0857089 ]
     [ 0.26047601  0.64166617  0.          0.14982485  0.84893827  0.32955081
       0.61937849  0.67239782  0.38699906  0.98894936  0.37038179  0.2497721
       0.81654559  0.40983286  0.2079005   0.65729823  0.99312398  0.3565001
       0.18791812  0.68968056]
     [ 0.37674972  0.46235433  0.14982485  0.          0.27922449  0.60604181
       0.16859335  0.76594887  0.93641621  0.93214304  0.0227043   0.44926752
       0.69535566  0.41551407  0.80478389  0.78461857  0.5007378   0.4972592
       0.77019143  0.66383516]
     [ 0.45137647  0.40113122  0.84893827  0.27922449  0.          0.42177412
       0.52515252  0.9673966   0.4184376   0.68636244  0.97264111  0.41265073
       0.53566023  0.86701972  0.1230965   0.54793885  0.5753517   0.6700346
       0.49067099  0.5370204 ]
     [ 0.12310214  0.11796713  0.32955081  0.60604181  0.42177412  0.
       0.65821533  0.22053475  0.20461195  0.45498337  0.4882077   0.97975761
       0.31203426  0.48740807  0.64801674  0.97876114  0.6361017   0.52766083
       0.08785026  0.68770366]
     [ 0.37301223  0.41403366  0.61937849  0.16859335  0.52515252  0.65821533
       0.          0.28164466  0.61002089  0.62432787  0.93214595  0.02292111
       0.59019799  0.8903922   0.29642441  0.63462486  0.12387221  0.32507567
       0.11682221  0.45460741]
     [ 0.12944068  0.59592532  0.67239782  0.76594887  0.9673966   0.22053475
       0.28164466  0.          0.75195262  0.57221404  0.287377    0.010693
       0.25914561  0.31709218  0.71239402  0.70580991  0.74098362  0.45667157
       0.45599442  0.76969444]
     [ 0.82038836  0.09973676  0.38699906  0.93641621  0.4184376   0.20461195
       0.61002089  0.75195262  0.          0.53066047  0.02292441  0.02937491
       0.68009449  0.75556352  0.30087734  0.51877403  0.71520217  0.69276597
       0.65884562  0.51128967]
     [ 0.2288873   0.01654451  0.98894936  0.93214304  0.68636244  0.45498337
       0.62432787  0.57221404  0.53066047  0.          0.30896103  0.31508832
       0.17556034  0.59715986  0.70365335  0.66405609  0.64245624  0.78978597
       0.01860635  0.27931224]
     [ 0.59478359  0.09593887  0.37038179  0.0227043   0.97264111  0.4882077
       0.93214595  0.287377    0.02292441  0.30896103  0.          0.35938869
       0.20794781  0.97691442  0.10405018  0.89608583  0.86043701  0.00460614
       0.46790977  0.44742079]
     [ 0.85289978  0.83879627  0.2497721   0.44926752  0.41265073  0.97975761
       0.02292111  0.010693    0.02937491  0.31508832  0.35938869  0.
       0.42787694  0.03522117  0.50791668  0.97356121  0.70048617  0.33771074
       0.69787944  0.04358689]
     [ 0.14622723  0.73259152  0.81654559  0.69535566  0.53566023  0.31203426
       0.59019799  0.25914561  0.68009449  0.17556034  0.20794781  0.42787694
       0.          0.71701941  0.5246826   0.06630206  0.36115521  0.94873697
       0.35789325  0.78514831]
     [ 0.57401177  0.56065718  0.40983286  0.41551407  0.86701972  0.48740807
       0.8903922   0.31709218  0.75556352  0.59715986  0.97691442  0.03522117
       0.71701941  0.          0.95369593  0.25212466  0.89292043  0.66258026
       0.24374489  0.79021815]
     [ 0.590426    0.13876812  0.2079005   0.80478389  0.1230965   0.64801674
       0.29642441  0.71239402  0.30087734  0.70365335  0.10405018  0.50791668
       0.5246826   0.95369593  0.          0.73610711  0.30282689  0.713897
       0.1366243   0.19524552]
     [ 0.34044494  0.94225634  0.65729823  0.78461857  0.54793885  0.97876114
       0.63462486  0.70580991  0.51877403  0.66405609  0.89608583  0.97356121
       0.06630206  0.25212466  0.73610711  0.          0.62771234  0.37166032
       0.4800879   0.18575952]
     [ 0.9195404   0.63069955  0.99312398  0.5007378   0.5753517   0.6361017
       0.12387221  0.74098362  0.71520217  0.64245624  0.86043701  0.70048617
       0.36115521  0.89292043  0.30282689  0.62771234  0.          0.48346746
       0.3090401   0.58710129]
     [ 0.86154929  0.43348979  0.3565001   0.4972592   0.6700346   0.52766083
       0.32507567  0.45667157  0.69276597  0.78978597  0.00460614  0.33771074
       0.94873697  0.66258026  0.713897    0.37166032  0.48346746  0.
       0.47776883  0.55045892]
     [ 0.40517876  0.86260898  0.18791812  0.77019143  0.49067099  0.08785026
       0.11682221  0.45599442  0.65884562  0.01860635  0.46790977  0.69787944
       0.35789325  0.24374489  0.1366243   0.4800879   0.3090401   0.47776883
       0.          0.30461071]
     [ 0.17091717  0.0857089   0.68968056  0.66383516  0.5370204   0.68770366
       0.45460741  0.76969444  0.51128967  0.27931224  0.44742079  0.04358689
       0.78514831  0.79021815  0.19524552  0.18575952  0.58710129  0.55045892
       0.30461071  0.        ]]
    and distance matrix
    [[ 0.          0.96671784  0.89723652  0.33622174  0.84025508  0.5430262
       0.44799682  0.85987871  0.35205354  0.77678375  0.13755356  0.23550748
       0.58986877  0.06126996  0.24534982  0.98472874  0.03777169  0.75356885
       0.34352588  0.39465901]
     [ 0.96671784  0.          0.27459243  0.87137165  0.61058827  0.70218436
       0.34234521  0.19986426  0.73459622  0.4813845   0.49730633  0.89733326
       0.75872436  0.47147793  0.09446113  0.13409924  0.63956822  0.15584706
       0.6830463   0.56610253]
     [ 0.89723652  0.27459243  0.          0.47745445  0.14014442  0.63407411
       0.39504264  0.80998032  0.54475875  0.98498291  0.56294193  0.97645137
       0.04434843  0.02988663  0.63079895  0.24931601  0.03094003  0.24734495
       0.11323619  0.88619157]
     [ 0.33622174  0.87137165  0.47745445  0.          0.69082862  0.06097423
       0.91331798  0.2168039   0.69092822  0.27799911  0.92146396  0.41926869
       0.37255732  0.32183137  0.41990931  0.69738845  0.61891328  0.52898815
       0.03036163  0.27398912]
     [ 0.84025508  0.61058827  0.14014442  0.69082862  0.          0.03620003
       0.35565985  0.59171331  0.7511281   0.90787154  0.7262593   0.99000306
       0.5592529   0.01927573  0.8083001   0.40020303  0.81869185  0.14017416
       0.12024818  0.11096786]
     [ 0.5430262   0.70218436  0.63407411  0.06097423  0.03620003  0.
       0.65487115  0.9131155   0.82367798  0.98098654  0.39590861  0.63502397
       0.71659353  0.78986598  0.25714442  0.21992478  0.16947211  0.61153307
       0.62260923  0.58231442]
     [ 0.44799682  0.34234521  0.39504264  0.91331798  0.35565985  0.65487115
       0.          0.25084592  0.42012132  0.40181586  0.01176334  0.24418595
       0.32567996  0.59889205  0.00731223  0.80306929  0.92416757  0.30374602
       0.36456449  0.98614193]
     [ 0.85987871  0.19986426  0.80998032  0.2168039   0.59171331  0.9131155
       0.25084592  0.          0.56151186  0.74069274  0.91447937  0.47452105
       0.60723543  0.26646301  0.40866186  0.91999989  0.10915717  0.41252722
       0.23650765  0.54989765]
     [ 0.35205354  0.73459622  0.54475875  0.69092822  0.7511281   0.82367798
       0.42012132  0.56151186  0.          0.09382583  0.42501446  0.96450068
       0.26075358  0.76147622  0.30633954  0.99155064  0.87505778  0.49916739
       0.18565243  0.15714958]
     [ 0.77678375  0.4813845   0.98498291  0.27799911  0.90787154  0.98098654
       0.40181586  0.74069274  0.09382583  0.          0.07863006  0.53771132
       0.94859677  0.39215369  0.1835277   0.62640496  0.54059929  0.807265
       0.7073882   0.70186132]
     [ 0.13755356  0.49730633  0.56294193  0.92146396  0.7262593   0.39590861
       0.01176334  0.91447937  0.42501446  0.07863006  0.          0.70816525
       0.96429992  0.25012843  0.32044867  0.94877521  0.77594899  0.28833066
       0.44916731  0.55779208]
     [ 0.23550748  0.89733326  0.97645137  0.41926869  0.99000306  0.63502397
       0.24418595  0.47452105  0.96450068  0.53771132  0.70816525  0.
       0.69071378  0.5439443   0.46802482  0.72737056  0.5153912   0.10762994
       0.54187015  0.07462942]
     [ 0.58986877  0.75872436  0.04434843  0.37255732  0.5592529   0.71659353
       0.32567996  0.60723543  0.26075358  0.94859677  0.96429992  0.69071378
       0.          0.66185164  0.44625349  0.74475672  0.2053439   0.55549468
       0.16429131  0.84770034]
     [ 0.06126996  0.47147793  0.02988663  0.32183137  0.01927573  0.78986598
       0.59889205  0.26646301  0.76147622  0.39215369  0.25012843  0.5439443
       0.66185164  0.          0.11104445  0.03363282  0.0379104   0.2195589
       0.88503606  0.22428301]
     [ 0.24534982  0.09446113  0.63079895  0.41990931  0.8083001   0.25714442
       0.00731223  0.40866186  0.30633954  0.1835277   0.32044867  0.46802482
       0.44625349  0.11104445  0.          0.1391679   0.65780252  0.61118467
       0.9849599   0.12343636]
     [ 0.98472874  0.13409924  0.24931601  0.69738845  0.40020303  0.21992478
       0.80306929  0.91999989  0.99155064  0.62640496  0.94877521  0.72737056
       0.74475672  0.03363282  0.1391679   0.          0.61867302  0.04790221
       0.06299265  0.56801753]
     [ 0.03777169  0.63956822  0.03094003  0.61891328  0.81869185  0.16947211
       0.92416757  0.10915717  0.87505778  0.54059929  0.77594899  0.5153912
       0.2053439   0.0379104   0.65780252  0.61867302  0.          0.44528865
       0.27458003  0.25899291]
     [ 0.75356885  0.15584706  0.24734495  0.52898815  0.14017416  0.61153307
       0.30374602  0.41252722  0.49916739  0.807265    0.28833066  0.10762994
       0.55549468  0.2195589   0.61118467  0.04790221  0.44528865  0.
       0.3702548   0.84087004]
     [ 0.34352588  0.6830463   0.11323619  0.03036163  0.12024818  0.62260923
       0.36456449  0.23650765  0.18565243  0.7073882   0.44916731  0.54187015
       0.16429131  0.88503606  0.9849599   0.06299265  0.27458003  0.3702548
       0.          0.35757854]
     [ 0.39465901  0.56610253  0.88619157  0.27398912  0.11096786  0.58231442
       0.98614193  0.54989765  0.15714958  0.70186132  0.55779208  0.07462942
       0.84770034  0.22428301  0.12343636  0.56801753  0.25899291  0.84087004
       0.35757854  0.        ]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]]
    >>> random(40)
    QAP of size 40 with the flow matrix
    [[ 0.          0.12696983  0.26047601 ...,  0.0857089   0.14982485
       0.84893827]
     [ 0.12696983  0.          0.32955081 ...,  0.68636244  0.97264111
       0.41265073]
     [ 0.26047601  0.32955081  0.         ...,  0.45460741  0.75195262
       0.57221404]
     ..., 
     [ 0.0857089   0.68636244  0.45460741 ...,  0.          0.25858789
       0.27792168]
     [ 0.14982485  0.97264111  0.75195262 ...,  0.25858789  0.          0.20844865]
     [ 0.84893827  0.41265073  0.57221404 ...,  0.27792168  0.20844865  0.        ]]
    and distance matrix
    [[ 0.          0.96671784  0.89723652 ...,  0.56610253  0.47745445
       0.14014442]
     [ 0.96671784  0.          0.63407411 ...,  0.90787154  0.7262593
       0.99000306]
     [ 0.89723652  0.63407411  0.         ...,  0.98614193  0.56151186
       0.74069274]
     ..., 
     [ 0.56610253  0.90787154  0.98614193 ...,  0.          0.55033341
       0.13991545]
     [ 0.47745445  0.7262593   0.56151186 ...,  0.55033341  0.          0.45005072]
     [ 0.14014442  0.99000306  0.74069274 ...,  0.13991545  0.45005072  0.        ]]
    and linear cost matrix
    [[ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    >>> random(50)
    QAP of size 50 with the flow matrix
    [[ 0.          0.12696983  0.26047601 ...,  0.81654559  0.40983286
       0.2079005 ]
     [ 0.12696983  0.          0.65729823 ...,  0.97876114  0.6361017
       0.52766083]
     [ 0.26047601  0.65729823  0.         ...,  0.64245624  0.78978597
       0.01860635]
     ..., 
     [ 0.81654559  0.97876114  0.64245624 ...,  0.          0.67540589
       0.57024253]
     [ 0.40983286  0.6361017   0.78978597 ...,  0.67540589  0.          0.69207373]
     [ 0.2079005   0.52766083  0.01860635 ...,  0.57024253  0.69207373  0.        ]]
    and distance matrix
    [[ 0.          0.96671784  0.89723652 ...,  0.04434843  0.02988663
       0.63079895]
     [ 0.96671784  0.          0.24931601 ...,  0.21992478  0.16947211
       0.61153307]
     [ 0.89723652  0.24931601  0.         ...,  0.54059929  0.807265    0.7073882 ]
     ..., 
     [ 0.04434843  0.21992478  0.54059929 ...,  0.          0.94331538
       0.66133937]
     [ 0.02988663  0.16947211  0.807265   ...,  0.94331538  0.          0.0118806 ]
     [ 0.63079895  0.61153307  0.7073882  ...,  0.66133937  0.0118806   0.        ]]
    and linear cost matrix
    [[ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    >>> random(100)
    QAP of size 100 with the flow matrix
    [[ 0.          0.12696983  0.26047601 ...,  0.52766083  0.08785026
       0.68770366]
     [ 0.12696983  0.          0.28164466 ...,  0.52650576  0.86081306
       0.48651369]
     [ 0.26047601  0.28164466  0.         ...,  0.38360523  0.56029581
       0.45564378]
     ..., 
     [ 0.52766083  0.52650576  0.38360523 ...,  0.          0.04302309
       0.20187473]
     [ 0.08785026  0.86081306  0.56029581 ...,  0.04302309  0.          0.07722681]
     [ 0.68770366  0.48651369  0.45564378 ...,  0.20187473  0.07722681  0.        ]]
    and distance matrix
    [[ 0.          0.96671784  0.89723652 ...,  0.61153307  0.62260923
       0.58231442]
     [ 0.96671784  0.          0.25084592 ...,  0.32332088  0.51873586
       0.38472384]
     [ 0.89723652  0.25084592  0.         ...,  0.0139871   0.60392746
       0.3825841 ]
     ..., 
     [ 0.61153307  0.32332088  0.0139871  ...,  0.          0.3547607
       0.2571106 ]
     [ 0.62260923  0.51873586  0.60392746 ...,  0.3547607   0.          0.54966467]
     [ 0.58231442  0.38472384  0.3825841  ...,  0.2571106   0.54966467  0.        ]]
    and linear cost matrix
    [[ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    """
    #initialize
    np.random.seed(seed)
    f = np.empty((n,n))
    d = np.empty((n,n))
    
    #set the random entries
    for i in xrange(n):
        for j in xrange(n):
            if i == j:
                f[i,j] = 0
                d[i,j] = 0
            elif i < j:
                f[i,j] = np.random.random()
                d[i,j] = np.random.random()
            else:
                f[i,j] = f[j,i]
                d[i,j] = d[j,i]
        
    return classes.Problem(f,d)

def random_asymmetric(n, linear_term = False,  seed = vars.seed_standard):
    """
    Returns a random, asymmetric Problem of size n.
    
    Examples:
    
    >>> random_asymmetric(5)
    QAP of size 5 with the flow matrix
    [[ 0.12696983  0.96671784  0.26047601  0.89723652  0.37674972]
     [ 0.33622174  0.45137647  0.84025508  0.12310214  0.5430262 ]
     [ 0.37301223  0.44799682  0.12944068  0.85987871  0.82038836]
     [ 0.35205354  0.2288873   0.77678375  0.59478359  0.13755356]
     [ 0.85289978  0.23550748  0.14622723  0.58986877  0.57401177]]
    and distance matrix
    [[ 0.06126996  0.590426    0.24534982  0.34044494  0.98472874]
     [ 0.9195404   0.03777169  0.86154929  0.75356885  0.40517876]
     [ 0.34352588  0.17091717  0.39465901  0.64166617  0.27459243]
     [ 0.46235433  0.87137165  0.40113122  0.61058827  0.11796713]
     [ 0.70218436  0.41403366  0.34234521  0.59592532  0.19986426]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.]]
    >>> random_asymmetric(10)
    QAP of size 10 with the flow matrix
    [[ 0.12696983  0.96671784  0.26047601  0.89723652  0.37674972  0.33622174
       0.45137647  0.84025508  0.12310214  0.5430262 ]
     [ 0.37301223  0.44799682  0.12944068  0.85987871  0.82038836  0.35205354
       0.2288873   0.77678375  0.59478359  0.13755356]
     [ 0.85289978  0.23550748  0.14622723  0.58986877  0.57401177  0.06126996
       0.590426    0.24534982  0.34044494  0.98472874]
     [ 0.9195404   0.03777169  0.86154929  0.75356885  0.40517876  0.34352588
       0.17091717  0.39465901  0.64166617  0.27459243]
     [ 0.46235433  0.87137165  0.40113122  0.61058827  0.11796713  0.70218436
       0.41403366  0.34234521  0.59592532  0.19986426]
     [ 0.09973676  0.73459622  0.01654451  0.4813845   0.09593887  0.49730633
       0.83879627  0.89733326  0.73259152  0.75872436]
     [ 0.56065718  0.47147793  0.13876812  0.09446113  0.94225634  0.13409924
       0.63069955  0.63956822  0.43348979  0.15584706]
     [ 0.86260898  0.6830463   0.0857089   0.56610253  0.14982485  0.47745445
       0.84893827  0.14014442  0.32955081  0.63407411]
     [ 0.61937849  0.39504264  0.67239782  0.80998032  0.38699906  0.54475875
       0.98894936  0.98498291  0.37038179  0.56294193]
     [ 0.2497721   0.97645137  0.81654559  0.04434843  0.40983286  0.02988663
       0.2079005   0.63079895  0.65729823  0.24931601]]
    and distance matrix
    [[ 0.99312398  0.03094003  0.3565001   0.24734495  0.18791812  0.11323619
       0.68968056  0.88619157  0.27922449  0.69082862]
     [ 0.60604181  0.06097423  0.16859335  0.91331798  0.76594887  0.2168039
       0.93641621  0.69092822  0.93214304  0.27799911]
     [ 0.0227043   0.92146396  0.44926752  0.41926869  0.69535566  0.37255732
       0.41551407  0.32183137  0.80478389  0.41990931]
     [ 0.78461857  0.69738845  0.5007378   0.61891328  0.4972592   0.52898815
       0.77019143  0.03036163  0.66383516  0.27398912]
     [ 0.42177412  0.03620003  0.52515252  0.35565985  0.9673966   0.59171331
       0.4184376   0.7511281   0.68636244  0.90787154]
     [ 0.97264111  0.7262593   0.41265073  0.99000306  0.53566023  0.5592529
       0.86701972  0.01927573  0.1230965   0.8083001 ]
     [ 0.54793885  0.40020303  0.5753517   0.81869185  0.6700346   0.14017416
       0.49067099  0.12024818  0.5370204   0.11096786]
     [ 0.65821533  0.65487115  0.22053475  0.9131155   0.20461195  0.82367798
       0.45498337  0.98098654  0.4882077   0.39590861]
     [ 0.97975761  0.63502397  0.31203426  0.71659353  0.48740807  0.78986598
       0.64801674  0.25714442  0.97876114  0.21992478]
     [ 0.6361017   0.16947211  0.52766083  0.61153307  0.08785026  0.62260923
       0.68770366  0.58231442  0.28164466  0.25084592]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]
    >>> random_asymmetric(20, True)
    QAP of size 20 with the flow matrix
    [[ 0.12696983  0.96671784  0.26047601  0.89723652  0.37674972  0.33622174
       0.45137647  0.84025508  0.12310214  0.5430262   0.37301223  0.44799682
       0.12944068  0.85987871  0.82038836  0.35205354  0.2288873   0.77678375
       0.59478359  0.13755356]
     [ 0.85289978  0.23550748  0.14622723  0.58986877  0.57401177  0.06126996
       0.590426    0.24534982  0.34044494  0.98472874  0.9195404   0.03777169
       0.86154929  0.75356885  0.40517876  0.34352588  0.17091717  0.39465901
       0.64166617  0.27459243]
     [ 0.46235433  0.87137165  0.40113122  0.61058827  0.11796713  0.70218436
       0.41403366  0.34234521  0.59592532  0.19986426  0.09973676  0.73459622
       0.01654451  0.4813845   0.09593887  0.49730633  0.83879627  0.89733326
       0.73259152  0.75872436]
     [ 0.56065718  0.47147793  0.13876812  0.09446113  0.94225634  0.13409924
       0.63069955  0.63956822  0.43348979  0.15584706  0.86260898  0.6830463
       0.0857089   0.56610253  0.14982485  0.47745445  0.84893827  0.14014442
       0.32955081  0.63407411]
     [ 0.61937849  0.39504264  0.67239782  0.80998032  0.38699906  0.54475875
       0.98894936  0.98498291  0.37038179  0.56294193  0.2497721   0.97645137
       0.81654559  0.04434843  0.40983286  0.02988663  0.2079005   0.63079895
       0.65729823  0.24931601]
     [ 0.99312398  0.03094003  0.3565001   0.24734495  0.18791812  0.11323619
       0.68968056  0.88619157  0.27922449  0.69082862  0.60604181  0.06097423
       0.16859335  0.91331798  0.76594887  0.2168039   0.93641621  0.69092822
       0.93214304  0.27799911]
     [ 0.0227043   0.92146396  0.44926752  0.41926869  0.69535566  0.37255732
       0.41551407  0.32183137  0.80478389  0.41990931  0.78461857  0.69738845
       0.5007378   0.61891328  0.4972592   0.52898815  0.77019143  0.03036163
       0.66383516  0.27398912]
     [ 0.42177412  0.03620003  0.52515252  0.35565985  0.9673966   0.59171331
       0.4184376   0.7511281   0.68636244  0.90787154  0.97264111  0.7262593
       0.41265073  0.99000306  0.53566023  0.5592529   0.86701972  0.01927573
       0.1230965   0.8083001 ]
     [ 0.54793885  0.40020303  0.5753517   0.81869185  0.6700346   0.14017416
       0.49067099  0.12024818  0.5370204   0.11096786  0.65821533  0.65487115
       0.22053475  0.9131155   0.20461195  0.82367798  0.45498337  0.98098654
       0.4882077   0.39590861]
     [ 0.97975761  0.63502397  0.31203426  0.71659353  0.48740807  0.78986598
       0.64801674  0.25714442  0.97876114  0.21992478  0.6361017   0.16947211
       0.52766083  0.61153307  0.08785026  0.62260923  0.68770366  0.58231442
       0.28164466  0.25084592]
     [ 0.61002089  0.42012132  0.62432787  0.40181586  0.93214595  0.01176334
       0.02292111  0.24418595  0.59019799  0.32567996  0.8903922   0.59889205
       0.29642441  0.00731223  0.63462486  0.80306929  0.12387221  0.92416757
       0.32507567  0.30374602]
     [ 0.11682221  0.36456449  0.45460741  0.98614193  0.75195262  0.56151186
       0.57221404  0.74069274  0.287377    0.91447937  0.010693    0.47452105
       0.25914561  0.60723543  0.31709218  0.26646301  0.71239402  0.40866186
       0.70580991  0.91999989]
     [ 0.74098362  0.10915717  0.45667157  0.41252722  0.45599442  0.23650765
       0.76969444  0.54989765  0.53066047  0.09382583  0.02292441  0.42501446
       0.02937491  0.96450068  0.68009449  0.26075358  0.75556352  0.76147622
       0.30087734  0.30633954]
     [ 0.51877403  0.99155064  0.71520217  0.87505778  0.69276597  0.49916739
       0.65884562  0.18565243  0.51128967  0.15714958  0.30896103  0.07863006
       0.31508832  0.53771132  0.17556034  0.94859677  0.59715986  0.39215369
       0.70365335  0.1835277 ]
     [ 0.66405609  0.62640496  0.64245624  0.54059929  0.78978597  0.807265
       0.01860635  0.7073882   0.27931224  0.70186132  0.35938869  0.70816525
       0.20794781  0.96429992  0.97691442  0.25012843  0.10405018  0.32044867
       0.89608583  0.94877521]
     [ 0.86043701  0.77594899  0.00460614  0.28833066  0.46790977  0.44916731
       0.44742079  0.55779208  0.42787694  0.69071378  0.03522117  0.5439443
       0.50791668  0.46802482  0.97356121  0.72737056  0.70048617  0.5153912
       0.33771074  0.10762994]
     [ 0.69787944  0.54187015  0.04358689  0.07462942  0.71701941  0.66185164
       0.5246826   0.44625349  0.06630206  0.74475672  0.36115521  0.2053439
       0.94873697  0.55549468  0.35789325  0.16429131  0.78514831  0.84770034
       0.95369593  0.11104445]
     [ 0.25212466  0.03363282  0.89292043  0.0379104   0.66258026  0.2195589
       0.24374489  0.88503606  0.79021815  0.22428301  0.73610711  0.1391679
       0.30282689  0.65780252  0.713897    0.61118467  0.1366243   0.9849599
       0.19524552  0.12343636]
     [ 0.62771234  0.61867302  0.37166032  0.04790221  0.4800879   0.06299265
       0.18575952  0.56801753  0.48346746  0.44528865  0.3090401   0.27458003
       0.58710129  0.25899291  0.47776883  0.3702548   0.55045892  0.84087004
       0.30461071  0.35757854]
     [ 0.22980025  0.59600066  0.30905882  0.95792315  0.96566315  0.12310195
       0.33691433  0.31861612  0.52650576  0.32332088  0.86081306  0.51873586
       0.48651369  0.38472384  0.19080443  0.50572254  0.61453327  0.8919388
       0.6239769   0.67663852]]
    and distance matrix
    [[ 0.48055909  0.37852789  0.4608584   0.42022312  0.13640368  0.14129451
       0.73220598  0.41954007  0.60467487  0.60446553  0.84897398  0.89616498
       0.58916777  0.92004553  0.73271562  0.31006212  0.93079     0.31271088
       0.6187646   0.95351446]
     [ 0.32106611  0.66341627  0.39563784  0.52433377  0.51672953  0.89413116
       0.97143796  0.14135297  0.52783029  0.86167095  0.95467052  0.80130654
       0.29377041  0.07745348  0.49668391  0.19808942  0.325444    0.24841208
       0.75179027  0.13177808]
     [ 0.36595759  0.61706068  0.1042514   0.92715643  0.16346328  0.96126524
       0.38334264  0.77186504  0.12778838  0.49085611  0.48090321  0.13432719
       0.72259881  0.43570061  0.0702726   0.91503527  0.21581449  0.52139452
       0.4338506   0.90097287]
     [ 0.52615659  0.23850945  0.03208453  0.80847815  0.56724767  0.98669892
       0.1049692   0.78610254  0.81722355  0.43327052  0.16229171  0.58535009
       0.19907896  0.94387607  0.26621431  0.78881428  0.30116144  0.89844679
       0.4572717   0.95098408]
     [ 0.94016597  0.86674457  0.85403571  0.58007797  0.62043857  0.43444547
       0.90758201  0.11783378  0.7386131   0.0716803   0.28231001  0.64284324
       0.26077645  0.2907511   0.46207961  0.68762394  0.53241766  0.38726327
       0.16594773  0.90225984]
     [ 0.82500685  0.82745302  0.93611433  0.95692457  0.58302646  0.32759054
       0.85059727  0.63710489  0.23229433  0.76926534  0.43695531  0.12979529
       0.13820581  0.94191858  0.72337317  0.59013609  0.51094959  0.70064824
       0.06039176  0.67412602]
     [ 0.94429031  0.11424667  0.45350473  0.06737038  0.62341901  0.12488089
       0.31757116  0.39695316  0.25611976  0.94564968  0.26202501  0.17815929
       0.04839178  0.23955357  0.19840228  0.33408413  0.5553091   0.26972356
       0.73550271  0.87022657]
     [ 0.57017375  0.68061546  0.65036836  0.08576089  0.97965549  0.83213318
       0.05693315  0.11284629  0.67497956  0.95350382  0.97953509  0.98479454
       0.11168017  0.41221021  0.97195203  0.31175199  0.44413408  0.98954302
       0.05204525  0.52252851]
     [ 0.20990188  0.56701219  0.21602174  0.36605794  0.50306284  0.47913618
       0.65291485  0.52454313  0.23826499  0.96528775  0.82709119  0.80632297
       0.01375995  0.36437775  0.97702648  0.62183949  0.74342053  0.80304977
       0.73437284  0.23456562]
     [ 0.65775609  0.1119275   0.38360523  0.0139871   0.56029581  0.60392746
       0.45564378  0.3825841   0.43376981  0.26929192  0.99975174  0.96565961
       0.54564913  0.76319146  0.63351133  0.84143592  0.78086956  0.02969578
       0.70637802  0.2488805 ]
     [ 0.1325735   0.4888221   0.1192695   0.3609136   0.28232427  0.54577296
       0.72887327  0.23200721  0.91917464  0.14045968  0.92355152  0.6757537
       0.23352878  0.71246564  0.47403814  0.49043413  0.86959745  0.8407507
       0.03446869  0.18987448]
     [ 0.96436538  0.46530385  0.90577762  0.12783795  0.09999906  0.65486922
       0.99331895  0.34234769  0.95263895  0.76087847  0.74891224  0.44750818
       0.78033037  0.22290209  0.58510473  0.66054113  0.68948917  0.51272078
       0.25638021  0.02207648]
     [ 0.66820684  0.92315158  0.14116027  0.78469668  0.02196311  0.42675597
       0.74722635  0.63569032  0.03266157  0.17133487  0.89375938  0.78168
       0.49805692  0.31968141  0.94013724  0.26542372  0.4178845   0.47187909
       0.98450056  0.93086829]
     [ 0.19162678  0.08696618  0.04460306  0.24304508  0.320884    0.21197946
       0.50670981  0.60908536  0.05135822  0.75030673  0.51231313  0.32441801
       0.69386562  0.12151679  0.69242358  0.60375601  0.81081401  0.47553087
       0.05960466  0.14910673]
     [ 0.88479629  0.14947466  0.90966013  0.4336029   0.32297187  0.44619757
       0.86119848  0.54717373  0.30604769  0.07056213  0.96140405  0.83120544
       0.34593972  0.60048473  0.80479227  0.84324343  0.03808699  0.10532186
       0.9989288   0.09836243]
     [ 0.95053791  0.99445977  0.16242876  0.76759965  0.25865688  0.7300598
       0.9317139   0.33446895  0.30427973  0.58306091  0.85140998  0.85582821
       0.23478573  0.34260125  0.5345584   0.30989183  0.72427011  0.74394516
       0.77528197  0.81726434]
     [ 0.17950795  0.74220045  0.54454876  0.91502105  0.54283133  0.13401617
       0.80355038  0.1819928   0.24025874  0.2725738   0.16776274  0.42021612
       0.19436097  0.97320607  0.28375437  0.49138337  0.57067524  0.29190174
       0.35058357  0.43175214]
     [ 0.29415188  0.43210958  0.3517591   0.34096186  0.97737352  0.24221143
       0.11721371  0.72833968  0.39324404  0.22017658  0.08432447  0.60192387
       0.45246884  0.51336399  0.59403732  0.65568111  0.25274548  0.27936333
       0.29830896  0.56878839]
     [ 0.46052323  0.99328392  0.31273823  0.48323466  0.30117491  0.24717469
       0.4331579   0.34517476  0.15712375  0.12697361  0.90129329  0.80401068
       0.05529574  0.70296533  0.12432326  0.23566225  0.56565783  0.29951398
       0.05890698  0.06697871]
     [ 0.81727597  0.86997237  0.77761719  0.35361771  0.8196606   0.18491487
       0.8021749   0.59100508  0.28858215  0.67009248  0.90715392  0.22493829
       0.01318174  0.8973749   0.75472374  0.24179905  0.9749598   0.94153824
       0.96610645  0.94420762]]
    and linear cost matrix
    [[  4.28642123e-02   5.73021442e-02   2.87699961e-02   6.40007295e-01
        4.15713377e-01   8.39013092e-01   2.84150423e-01   8.07420310e-01
        5.55203531e-01   9.57745744e-01   9.15562960e-01   8.86303036e-01
        1.83253811e-01   9.49166266e-02   1.63061731e-02   2.59081731e-01
        3.59482982e-01   8.95407299e-01   9.75184564e-01   3.17925349e-01]
     [  2.86007901e-01   7.84510229e-01   3.96708365e-01   1.71870798e-01
        6.31375784e-01   7.65599538e-01   7.39904213e-01   1.89622347e-01
        6.08125977e-01   3.29363452e-01   1.81891436e-01   5.93789653e-01
        6.13063210e-01   5.05329417e-01   9.62178511e-01   2.82927916e-01
        6.93290852e-01   4.67514049e-01   8.57872490e-01   1.30638580e-01]
     [  6.12956605e-01   2.03613445e-01   4.31295192e-01   1.18943525e-01
        5.57685681e-01   3.55966933e-01   2.50980307e-01   9.45965040e-01
        9.00254989e-01   9.01442207e-01   7.13117576e-01   8.37605626e-01
        5.62932661e-01   7.38294424e-01   2.58157655e-02   5.14392818e-01
        4.18772179e-01   2.51562528e-01   6.85012446e-01   8.45336168e-01]
     [  8.14253239e-01   4.70758499e-01   9.05193017e-01   1.36579702e-01
        9.33591011e-02   2.02948394e-01   3.37647467e-01   3.48062554e-01
        4.59837932e-01   5.89002036e-01   6.26758109e-01   7.21490973e-02
        9.78355017e-01   5.52970423e-01   9.18826565e-01   7.06118118e-01
        6.11889658e-01   3.95953313e-01   5.26570370e-02   7.82762584e-01]
     [  1.39907081e-01   9.13853270e-01   9.24410462e-01   3.70974767e-01
        6.11651216e-01   9.81849168e-01   9.24683700e-01   5.72236371e-01
        2.34930399e-01   2.46041147e-01   2.52862344e-01   7.34781895e-01
        4.36590431e-01   6.86140516e-01   5.72731127e-01   7.93167175e-01
        4.85034291e-01   5.57163399e-02   5.64731471e-01   3.31582768e-01]
     [  5.58277633e-01   2.86777841e-02   4.97361202e-01   1.66184749e-01
        2.08793008e-01   4.49727674e-01   6.44651259e-01   2.42564671e-01
        9.87247114e-01   8.26892739e-01   9.59982806e-02   9.26639023e-01
        7.17371616e-01   1.72788032e-01   4.48503743e-01   7.56597059e-01
        9.07573337e-01   9.88637239e-01   2.97683801e-01   4.03146204e-01]
     [  2.80021840e-01   7.40539303e-01   9.41852301e-02   1.94774370e-01
        4.32112231e-01   3.29809159e-01   4.66271822e-01   3.13231640e-01
        3.00944470e-01   6.12965826e-01   3.84515281e-01   6.28946566e-01
        1.39891608e-01   8.66723269e-01   8.75446578e-01   3.23694878e-01
        6.45427264e-01   7.00977986e-01   8.58966376e-01   8.08736670e-01]
     [  4.28875097e-01   1.71702420e-01   3.36577639e-01   9.61591538e-01
        5.57494032e-01   3.32823203e-01   3.13171279e-02   3.57538180e-01
        8.75229047e-01   9.83178771e-02   1.15380893e-01   8.20418763e-01
        2.51352925e-01   3.45472853e-01   7.02960870e-01   9.94513224e-01
        9.27711302e-01   7.85067987e-01   2.95977169e-01   6.80676153e-02]
     [  9.22023943e-03   2.16373393e-01   9.60413177e-01   7.05494615e-01
        6.83511823e-01   9.60890817e-01   9.46658018e-01   2.74119694e-01
        3.04210637e-01   5.31731361e-01   2.93643284e-01   5.78298549e-01
        5.21581183e-01   8.96040812e-01   6.12535377e-01   8.22297258e-01
        2.54365175e-01   7.11934739e-01   7.19589610e-01   5.32168542e-01]
     [  6.28246403e-01   5.21338977e-01   6.45883130e-01   5.20625219e-01
        3.64217328e-01   7.15901515e-01   7.84180814e-01   2.55208740e-01
        8.15785331e-01   3.70252874e-01   4.40927864e-01   5.89658641e-01
        5.21681096e-01   8.63929981e-01   5.51679116e-01   7.16052074e-01
        6.89973929e-01   2.89803187e-01   2.85130740e-01   8.08178605e-01]
     [  9.07925987e-01   4.17923105e-01   8.01055596e-01   7.15707993e-01
        4.99659055e-01   3.06637532e-01   4.86932388e-01   7.85943290e-01
        7.67702175e-01   6.49306674e-01   8.12140209e-01   3.87469368e-01
        8.30729179e-01   4.48313968e-01   3.02147191e-01   2.41470567e-01
        9.02399426e-01   7.51911396e-01   7.99163277e-01   1.64197931e-01]
     [  9.81415751e-01   5.48957188e-01   8.37524284e-01   9.86367959e-01
        6.66037372e-01   7.36612328e-01   3.88745255e-01   6.94714296e-01
        4.02513662e-01   2.61937474e-01   8.60295134e-02   1.19187721e-01
        6.38374868e-01   5.34101939e-01   5.04227897e-01   6.94151066e-01
        8.78758537e-01   2.27884466e-01   6.88016758e-01   8.39528478e-01]
     [  7.70441621e-01   9.91646828e-01   7.59501413e-01   8.01309866e-01
        1.46646638e-01   1.53429758e-01   6.60488156e-01   4.74862072e-01
        1.92698085e-01   2.98026613e-01   4.65608343e-01   5.25622738e-01
        9.16134749e-01   4.28538268e-01   4.99455148e-01   9.60782362e-01
        5.69136662e-01   1.58765331e-01   4.21283851e-01   6.84970189e-01]
     [  3.70006958e-01   9.42753762e-01   9.00429419e-01   4.78029980e-01
        6.88127083e-01   9.03508264e-01   7.39073488e-01   3.30088107e-01
        1.22230591e-01   6.51778512e-02   7.63776662e-01   7.03621275e-01
        6.19113136e-01   7.36531757e-01   6.08906833e-01   5.70503580e-01
        1.25909513e-01   6.20591669e-01   5.91281860e-01   9.09998876e-01]
     [  9.69262556e-01   9.87089098e-01   9.52453492e-01   2.15536345e-01
        1.34102028e-01   9.54636903e-01   3.76946071e-01   4.94274906e-01
        5.49707118e-01   2.44183031e-01   5.34878759e-01   7.12996061e-01
        8.00632037e-01   9.65928083e-01   9.36388458e-01   2.83540654e-01
        9.02102215e-01   5.11059058e-01   4.74136337e-01   2.59505441e-01]
     [  6.41690898e-01   1.74368174e-01   3.30488574e-01   3.04035695e-02
        5.13529051e-01   5.18007240e-04   7.54566294e-02   9.82533237e-01
        9.12771333e-01   1.61477938e-01   5.74937484e-01   1.99199038e-01
        1.91645498e-01   7.38629631e-02   8.80433344e-01   4.38762638e-01
        5.18296593e-01   5.35454553e-01   3.92518064e-01   3.10567294e-01]
     [  4.10445587e-01   8.89700352e-01   1.24455224e-01   9.23879740e-01
        2.86260094e-02   2.59071439e-02   8.50310963e-01   1.44442794e-01
        7.22644271e-03   8.80909749e-01   2.82521103e-01   7.85895838e-01
        4.52238575e-01   5.02351308e-01   9.26350819e-01   7.59764144e-01
        6.85196630e-01   4.81952272e-01   8.55395883e-01   6.92017279e-01]
     [  1.32636689e-01   1.67629517e-01   6.29126611e-01   1.82157467e-01
        2.77532876e-01   4.80162259e-01   4.21949605e-02   9.94453234e-01
        7.71609467e-01   7.22952279e-01   4.68434913e-01   9.78921502e-01
        9.18563507e-01   3.25619447e-01   6.04079846e-01   1.53239482e-01
        5.66018538e-01   1.16384266e-01   5.96634635e-01   1.47251430e-03]
     [  9.28339380e-01   1.03840962e-01   6.82203084e-01   2.93063169e-01
        1.18562678e-01   1.48441057e-01   7.98417960e-01   7.10147990e-01
        9.83291250e-01   4.86234911e-01   9.32591083e-01   9.37896682e-01
        9.52811707e-01   1.86932661e-01   7.29430114e-01   7.43444416e-01
        2.48408168e-01   9.05846181e-01   2.05660758e-01   2.96818018e-01]
     [  3.71293960e-01   1.24694585e-01   9.44006901e-01   3.18414643e-02
        1.27188725e-01   7.26441184e-01   4.98826406e-01   8.23132232e-01
        4.59850480e-01   3.32593471e-01   4.58983839e-01   4.59955340e-01
        3.49546277e-01   2.29047016e-01   3.25784804e-01   5.28807172e-01
        5.52080878e-01   2.49445301e-01   5.87645508e-01   4.76636060e-01]]
    >>> random_asymmetric(40)
    QAP of size 40 with the flow matrix
    [[ 0.12696983  0.96671784  0.26047601 ...,  0.39465901  0.64166617
       0.27459243]
     [ 0.46235433  0.87137165  0.40113122 ...,  0.14014442  0.32955081
       0.63407411]
     [ 0.61937849  0.39504264  0.67239782 ...,  0.69092822  0.93214304
       0.27799911]
     ..., 
     [ 0.22133914  0.35703545  0.71592057 ...,  0.96268742  0.90541796
       0.91702336]
     [ 0.00894039  0.78209766  0.61547978 ...,  0.13991545  0.20844865
       0.45005072]
     [ 0.70776018  0.4845597   0.50750425 ...,  0.65715019  0.83522708
       0.6377381 ]]
    and distance matrix
    [[ 0.87085196  0.73890375  0.19319146 ...,  0.3142623   0.44815213
       0.61750766]
     [ 0.16963643  0.46457916  0.23872873 ...,  0.12258615  0.01776463
       0.37135586]
     [ 0.03229392  0.58752395  0.86917051 ...,  0.48200854  0.55613509
       0.48224318]
     ..., 
     [ 0.80115471  0.43543456  0.4776799  ...,  0.83670748  0.79584193
       0.5354502 ]
     [ 0.863322    0.09228121  0.93904267 ...,  0.67426692  0.80326663
       0.96132249]
     [ 0.04675007  0.11701463  0.97546254 ...,  0.22721231  0.18694896
       0.67857323]]
    and linear cost matrix
    [[ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    >>> random_asymmetric(50, True)
    QAP of size 50 with the flow matrix
    [[ 0.12696983  0.96671784  0.26047601 ...,  0.34234521  0.59592532
       0.19986426]
     [ 0.09973676  0.73459622  0.01654451 ...,  0.63079895  0.65729823
       0.24931601]
     [ 0.99312398  0.03094003  0.3565001  ...,  0.7511281   0.68636244
       0.90787154]
     ..., 
     [ 0.48371805  0.79877943  0.45713839 ...,  0.70657076  0.91976411
       0.21320135]
     [ 0.38061767  0.4195784   0.88020317 ...,  0.66133937  0.69207373
       0.0118806 ]
     [ 0.93421178  0.64781349  0.44153833 ...,  0.84851151  0.71410808
       0.53637633]]
    and distance matrix
    [[ 0.18813205  0.02913728  0.49522304 ...,  0.31450917  0.82361772
       0.52480473]
     [ 0.88113654  0.50917223  0.5682518  ...,  0.22432217  0.52498298
       0.39349014]
     [ 0.13021386  0.06222706  0.74810879 ...,  0.71066884  0.2740705
       0.30365129]
     ..., 
     [ 0.30905253  0.70114498  0.0899285  ...,  0.64842452  0.67144669
       0.56843149]
     [ 0.8331518   0.39559445  0.30813375 ...,  0.05663383  0.76159837
       0.17342783]
     [ 0.21607871  0.32186788  0.7614927  ...,  0.85721774  0.19447551
       0.51329213]]
    and linear cost matrix
    [[ 0.81107173  0.87173051  0.50076038 ...,  0.67032739  0.56808437
       0.06144405]
     [ 0.75235176  0.87360679  0.40816366 ...,  0.75463217  0.30520992
       0.43402506]
     [ 0.7856488   0.82610485  0.52602162 ...,  0.25658186  0.29987096
       0.86558185]
     ..., 
     [ 0.43052559  0.90468194  0.4119184  ...,  0.40831586  0.63090059
       0.70146319]
     [ 0.10871661  0.8278029   0.84386662 ...,  0.66268628  0.82461858
       0.69068719]
     [ 0.7358276   0.76144152  0.95416213 ...,  0.85637927  0.47604158
       0.89225771]]
    >>> random_asymmetric(100)
    QAP of size 100 with the flow matrix
    [[ 0.12696983  0.96671784  0.26047601 ...,  0.63079895  0.65729823
       0.24931601]
     [ 0.99312398  0.03094003  0.3565001  ...,  0.58231442  0.28164466
       0.25084592]
     [ 0.61002089  0.42012132  0.62432787 ...,  0.32044867  0.89608583
       0.94877521]
     ..., 
     [ 0.54997791  0.46327159  0.38035509 ...,  0.60973431  0.10609531
       0.62566805]
     [ 0.53849988  0.99199738  0.00881562 ...,  0.2571106   0.07722681
       0.54966467]
     [ 0.83680487  0.7357126   0.42591839 ...,  0.21608273  0.4487888
       0.27228287]]
    and distance matrix
    [[ 0.39943044  0.81123827  0.71571783 ...,  0.77040528  0.79274582
       0.62417947]
     [ 0.32906372  0.32400431  0.07774405 ...,  0.23228146  0.69434721
       0.65284731]
     [ 0.06186402  0.2866624   0.95703949 ...,  0.96019623  0.52250708
       0.60483877]
     ..., 
     [ 0.94297292  0.44214943  0.67227366 ...,  0.40789727  0.1896391
       0.17825648]
     [ 0.17180062  0.47677523  0.68817778 ...,  0.32542738  0.90255858
       0.005416  ]
     [ 0.9573212   0.02126154  0.93623596 ...,  0.91918168  0.41977281
       0.65482783]]
    and linear cost matrix
    [[ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    """
    np.random.seed(seed)
    f = np.random.random((n, n))
    d = np.random.random((n, n))
    if linear_term:
        c = np.random.random((n, n))
    else:
        c = np.zeros((n, n))
    return classes.Problem(f,d, c)

def reduced(problem, n,  name = None):
    '''
    Return a new problem of size n by extracting the upper left part of the
    matrix from the matrices in problem
    
    Examples:
    
    >>> reduced(QAPLIB('nug30'), 10)
    QAP of size 10 with the flow matrix
    [[ 0.  1.  2.  3.  4.  5.  1.  2.  3.  4.]
     [ 1.  0.  1.  2.  3.  4.  2.  1.  2.  3.]
     [ 2.  1.  0.  1.  2.  3.  3.  2.  1.  2.]
     [ 3.  2.  1.  0.  1.  2.  4.  3.  2.  1.]
     [ 4.  3.  2.  1.  0.  1.  5.  4.  3.  2.]
     [ 5.  4.  3.  2.  1.  0.  6.  5.  4.  3.]
     [ 1.  2.  3.  4.  5.  6.  0.  1.  2.  3.]
     [ 2.  1.  2.  3.  4.  5.  1.  0.  1.  2.]
     [ 3.  2.  1.  2.  3.  4.  2.  1.  0.  1.]
     [ 4.  3.  2.  1.  2.  3.  3.  2.  1.  0.]]
    and distance matrix
    [[  0.   3.   2.   0.   0.   2.  10.   5.   0.   5.]
     [  3.   0.   4.   0.  10.   4.   0.   0.   2.   2.]
     [  2.   4.   0.   3.   4.   0.   5.   5.   5.   1.]
     [  0.   0.   3.   0.   0.   0.   0.   2.   2.   0.]
     [  0.  10.   4.   0.   0.   5.   2.   0.   0.   0.]
     [  2.   4.   0.   0.   5.   0.   1.   2.   2.   1.]
     [ 10.   0.   5.   0.   2.   1.   0.  10.  10.   5.]
     [  5.   0.   5.   2.   0.   2.  10.   0.   1.   3.]
     [  0.   2.   5.   2.   0.   2.  10.   1.   0.  10.]
     [  5.   2.   1.   0.   0.   1.   5.   3.  10.   0.]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]
    >>> reduced(QAPLIB('sko100f'), 50)
    QAP of size 50 with the flow matrix
    [[  0.   1.   2. ...,  11.  12.  13.]
     [  1.   0.   1. ...,  10.  11.  12.]
     [  2.   1.   0. ...,   9.  10.  11.]
     ..., 
     [ 11.  10.   9. ...,   0.   1.   2.]
     [ 12.  11.  10. ...,   1.   0.   1.]
     [ 13.  12.  11. ...,   2.   1.   0.]]
    and distance matrix
    [[ 0.  5.  1. ...,  2.  6.  2.]
     [ 5.  0.  4. ...,  1.  5.  5.]
     [ 1.  4.  0. ...,  0.  6.  0.]
     ..., 
     [ 2.  1.  0. ...,  0.  2.  0.]
     [ 6.  5.  6. ...,  2.  0.  2.]
     [ 2.  5.  0. ...,  0.  2.  0.]]
    and linear cost matrix
    [[ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     ..., 
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]
     [ 0.  0.  0. ...,  0.  0.  0.]]
    >>> reduced(QAPLIB('esc32a'), 20)
    QAP of size 20 with the flow matrix
    [[ 0.  1.  1.  0.  0.  1.  0.  0.  0.  0.  1.  0.  4.  0.  0.  0.  0.  0.
       0.  0.]
     [ 1.  0.  1.  0.  2.  0.  0.  0.  1.  0.  0.  0.  0.  4.  0.  0.  0.  0.
       0.  0.]
     [ 1.  1.  0.  4.  0.  0.  0.  0.  3.  0.  0.  0.  0.  0.  3.  0.  0.  3.
       0.  0.]
     [ 0.  0.  4.  0.  1.  1.  0.  0.  3.  0.  0.  0.  0.  0.  3.  0.  0.  3.
       0.  0.]
     [ 0.  2.  0.  1.  0.  1.  0.  0.  1.  0.  0.  0.  0.  2.  0.  0.  0.  0.
       0.  0.]
     [ 1.  0.  0.  1.  1.  0.  0.  0.  0.  0.  1.  0.  1.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  3.  1.  0.
       0.  0.]
     [ 0.  1.  3.  3.  1.  0.  0.  0.  0.  0.  0.  0.  0.  1.  3.  0.  0.  3.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 1.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  1.  0.
       3.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  2.  1.  0.
       0.  0.]
     [ 4.  0.  0.  0.  0.  1.  0.  0.  0.  0.  1.  0.  0.  1.  1.  0.  0.  0.
       0.  0.]
     [ 0.  4.  0.  0.  2.  0.  0.  0.  1.  0.  0.  0.  1.  0.  1.  0.  0.  0.
       0.  0.]
     [ 0.  0.  3.  3.  0.  0.  0.  0.  3.  0.  0.  0.  1.  1.  0.  0.  0.  4.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  3.  0.  0.  0.  2.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  1.  1.  0.  0.  0.  0.  0.  0.
       1.  0.]
     [ 0.  0.  3.  3.  0.  0.  0.  0.  3.  0.  0.  0.  0.  0.  4.  0.  0.  0.
       2.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  3.  0.  0.  0.  0.  0.  1.  2.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]]
    and distance matrix
    [[ 0.  0.  0.  1.  0.  1.  1.  2.  0.  1.  1.  2.  1.  2.  2.  3.  0.  1.
       1.  2.]
     [ 0.  0.  1.  0.  1.  0.  2.  1.  1.  0.  2.  1.  2.  1.  3.  2.  1.  0.
       2.  1.]
     [ 0.  1.  0.  0.  1.  2.  0.  1.  1.  2.  0.  1.  2.  3.  1.  2.  1.  2.
       0.  1.]
     [ 1.  0.  0.  0.  2.  1.  1.  0.  2.  1.  1.  0.  3.  2.  2.  1.  2.  1.
       1.  0.]
     [ 0.  1.  1.  2.  0.  0.  0.  1.  1.  2.  2.  3.  0.  1.  1.  2.  1.  2.
       2.  3.]
     [ 1.  0.  2.  1.  0.  0.  1.  0.  2.  1.  3.  2.  1.  0.  2.  1.  2.  1.
       3.  2.]
     [ 1.  2.  0.  1.  0.  1.  0.  0.  2.  3.  1.  2.  1.  2.  0.  1.  2.  3.
       1.  2.]
     [ 2.  1.  1.  0.  1.  0.  0.  0.  3.  2.  2.  1.  2.  1.  1.  0.  3.  2.
       2.  1.]
     [ 0.  1.  1.  2.  1.  2.  2.  3.  0.  0.  0.  1.  0.  1.  1.  2.  1.  2.
       2.  3.]
     [ 1.  0.  2.  1.  2.  1.  3.  2.  0.  0.  1.  0.  1.  0.  2.  1.  2.  1.
       3.  2.]
     [ 1.  2.  0.  1.  2.  3.  1.  2.  0.  1.  0.  0.  1.  2.  0.  1.  2.  3.
       1.  2.]
     [ 2.  1.  1.  0.  3.  2.  2.  1.  1.  0.  0.  0.  2.  1.  1.  0.  3.  2.
       2.  1.]
     [ 1.  2.  2.  3.  0.  1.  1.  2.  0.  1.  1.  2.  0.  0.  0.  1.  2.  3.
       3.  4.]
     [ 2.  1.  3.  2.  1.  0.  2.  1.  1.  0.  2.  1.  0.  0.  1.  0.  3.  2.
       4.  3.]
     [ 2.  3.  1.  2.  1.  2.  0.  1.  1.  2.  0.  1.  0.  1.  0.  0.  3.  4.
       2.  3.]
     [ 3.  2.  2.  1.  2.  1.  1.  0.  2.  1.  1.  0.  1.  0.  0.  0.  4.  3.
       3.  2.]
     [ 0.  1.  1.  2.  1.  2.  2.  3.  1.  2.  2.  3.  2.  3.  3.  4.  0.  0.
       0.  1.]
     [ 1.  0.  2.  1.  2.  1.  3.  2.  2.  1.  3.  2.  3.  2.  4.  3.  0.  0.
       1.  0.]
     [ 1.  2.  0.  1.  2.  3.  1.  2.  2.  3.  1.  2.  3.  4.  2.  3.  0.  1.
       0.  0.]
     [ 2.  1.  1.  0.  3.  2.  2.  1.  3.  2.  2.  1.  4.  3.  3.  2.  1.  0.
       0.  0.]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
       0.  0.]]
    >>> reduced(QAPLIB('had16'), 8)
    QAP of size 8 with the flow matrix
    [[ 0.  1.  2.  2.  3.  4.  4.  5.]
     [ 1.  0.  1.  1.  2.  3.  3.  4.]
     [ 2.  1.  0.  2.  1.  2.  2.  3.]
     [ 2.  1.  2.  0.  1.  2.  2.  3.]
     [ 3.  2.  1.  1.  0.  1.  1.  2.]
     [ 4.  3.  2.  2.  1.  0.  2.  3.]
     [ 4.  3.  2.  2.  1.  2.  0.  1.]
     [ 5.  4.  3.  3.  2.  3.  1.  0.]]
    and distance matrix
    [[ 0.  3.  4.  6.  8.  5.  6.  6.]
     [ 3.  0.  6.  3.  7.  9.  9.  2.]
     [ 4.  6.  0.  2.  6.  4.  4.  4.]
     [ 6.  3.  2.  0.  5.  5.  3.  3.]
     [ 8.  7.  6.  5.  0.  4.  3.  4.]
     [ 5.  9.  4.  5.  4.  0.  8.  5.]
     [ 6.  9.  4.  3.  3.  8.  0.  6.]
     [ 6.  2.  4.  3.  4.  5.  6.  0.]]
    and linear cost matrix
    [[ 0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.]]
    >>> reduced(QAPLIB('had16'), 20)
    Traceback (most recent call last):
      ...
    ValueError: The requested size is too big for the current problem.
    '''
    #check if n is smaller than or equal to the original problem
    if n > problem.n:
        raise ValueError("The requested size is too big for the current problem.")
        
    #initialize matrices to return
    new_f = np.empty((n, n))
    new_d = np.empty((n, n))
    
    #copy required portions of matrices
    
    #copy flow matrx
    for i in xrange(n):
        for j in xrange(n):
            new_f[i, j] = problem.f[i, j]
    
    #copy distance matrix
    for i in xrange(n):
        for j in xrange(n):
            new_d[i, j] = problem.d[i, j]
            
    return classes.Problem(new_f,  new_d)

def standard_test_suite(start=5, end=12, step=5):
    '''
    Return a standard test suite of problems with sizes ranging from start to
    end with a given step. If the parent problem isn't large enough, then as
    many problems as possible are generated until the size is exhausted.
    
    Examples:
    
    >>> [problem.n for problem in standard_test_suite()]
    [5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10]
    '''
    #list of base problems
    base_problems = ['nug30', 'chr25a', 'had20', 'rou20', 'scr20', 'wil100',\
                      'bur26a', 'esc64a', 'lipa30a' ,   'kra32', 'lipa90a',\
                      'sko100a', 'ste36a', 'tai256c', 'tho150']
    #add random problems
    l = [random(n) for n in xrange(start, end+1, step)]
    #add reduced versions of base problems
    for base in base_problems:
        b = QAPLIB(base)
        l += [reduced(b, n) for n in\
               xrange(start,  end+1,  step) if n <= b.n]
    return l
